package com.leetcode;

import com.leetcode.common.TreeNode;

/**
 * 235. 二叉搜索树的最近公共祖先
 * 深度优先搜索, 递归写法
 * 前一种的逻辑优化版本
 *
 * @author fy
 * @date 2022/4/25 20:35
 */
public class Solution235_1 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            throw new RuntimeException("node p or q is null");
        }
        if (root == null) {
            return null;
        }
        // 先判断p和q在root的同一侧的情况
        // 如果root的值都大于p和q值, 那么q和p都在root的左侧
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        // 如果root的值都小于p和q值, 那么q和p都在root的右侧
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        // 如果p和q在root的两侧或者p或者q和root重叠, 那么此时root肯定就是p和q的最早公共祖先
        // 在这里有一个默认的前提是p和q都在这颗二叉搜索树中, 不然需要判断q和p节点是否在树上
        return root;
    }

}
